📋 Problem Statement
You are managing a retail store and want to analyze your daily sales over the past few weeks. You've recorded the total sales for each day in an array. Your goal is to quickly find out the total sales within a range of days for reporting or planning.
To answer this efficiently, even for large datasets, you decide to preprocess the data using a Sparse Table and answer these queries in logarithmic time.
📥 Input Format
- First line:
N(number of days, 1 ≤ N ≤ 20) - Second line:
Nspace-separated integers (daily sales, 0 ≤ A[i] ≤ 100) - Third line:
Q(number of queries, 1 ≤ Q ≤ 20) - Next
Qlines: Two integersLandR(0 ≤ L ≤ R < N)
📤 Output Format
For each query, output a single integer representing the total sales from day L to day R, inclusive.
🎯 Sample Test Case 1
6 2 4 7 1 3 5 3 1 3 0 5 2 2
12 22 7
- Query [1, 3]: sum(4, 7, 1) = 4 + 7 + 1 = 12
- Query [0, 5]: sum(2, 4, 7, 1, 3, 5) = 2 + 4 + 7 + 1 + 3 + 5 = 22
- Query [2, 2]: sum(7) = 7
🎯 Sample Test Case 2
8 5 3 8 6 2 9 1 7 4 0 3 2 5 4 7 3 3
22 25 19 6
🧠 Sparse Table for Range Sum
A Sparse Table is a data structure that efficiently answers range queries on static arrays. For range sum queries, we preprocess the array to store sums of all power-of-2 length ranges.
📊 Key Concept
sparse[i][j] stores the sum of elements starting at index i and spanning 2^j elements.
For example:
sparse[i][0]= arr[i] (sum of 1 element)sparse[i][1]= arr[i] + arr[i+1] (sum of 2 elements)sparse[i][2]= sum of 4 elements starting at isparse[i][3]= sum of 8 elements starting at i
🔧 Building the Sparse Table
// Initialize for length 1 (2^0)
for (int i = 0; i < n; i++) {
sparse[i][0] = sales[i];
}
// Build for increasing powers of 2
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
// Sum of two halves
sparse[i][j] = sparse[i][j-1] +
sparse[i + (1 << (j-1))][j-1];
}
}
Time Complexity: O(n log n)
Space Complexity: O(n log n)
🔍 Querying Range Sum [L, R]
int querySum(int L, int R) {
int sum = 0;
int length = R - L + 1;
// Decompose range into powers of 2
for (int j = log2(n); j >= 0; j--) {
if ((1 << j) <= length) {
sum += sparse[L][j];
L += (1 << j);
length -= (1 << j);
}
}
return sum;
}
Time Complexity: O(log n) per query
📐 Range Decomposition Example
Query: [1, 6] (length = 6)
Length 6 = 4 + 2
= 2² + 2¹
Decomposition:
- sparse[1][2] covers [1, 4] (4 elements)
- sparse[5][1] covers [5, 6] (2 elements)
Total = sparse[1][2] + sparse[5][1]
⚡ Complexity Comparison
| Method | Preprocessing | Query Time | Space |
|---|---|---|---|
| Naive | O(1) | O(n) | O(1) |
| Prefix Sum | O(n) | O(1) | O(n) |
| Sparse Table | O(n log n) | O(log n) | O(n log n) |
Note: For pure range sum queries, prefix sums are optimal. However, Sparse Tables demonstrate a versatile technique useful for various range query problems and provide good practice for understanding power-of-2 decomposition.
💡 Key Insights
- Any positive integer can be uniquely represented as a sum of powers of 2 (binary representation)
- We decompose the query range into non-overlapping power-of-2 segments
- Each segment sum is precomputed in the sparse table
- Maximum number of segments needed = number of bits in length ≤ log₂(n)